package LC;

/**
 * https://leetcode.com/problems/number-of-islands/description/
 * Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
 * An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
 * You may assume all four edges of the grid are all surrounded by water.
 * Example 1:
 * 11110
 * 11010
 * 11000
 * 00000
 * Answer: 1
 * Example 2:
 * 11000
 * 11000
 * 00100
 * 00011
 * Answer: 3
 */
public class LC_200_NumberofIslands_BFS {

    public static void main(String[] args) {
        char[][] grid = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        System.out.println(Solution.numIslands(grid));
    }

    static class Solution {
        static int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            boolean[][] visited = new boolean[grid.length][grid[0].length];
            int result = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (!visited[i][j] && grid[i][j] == '1') {
                        result++;
                        bfs(grid, visited, i, j);
                    }
                }
            }
            return result;
        }

        static void bfs(char[][] grid, boolean[][] visited, int row, int col) {
            if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && !visited[row][col] && grid[row][col] == '1') {
                visited[row][col] = true;
                bfs(grid, visited, row - 1, col);
                bfs(grid, visited, row, col + 1);
                bfs(grid, visited, row + 1, col);
                bfs(grid, visited, row, col - 1);
            }
        }
    }
}